package william.tree;

import java.util.LinkedList;

/**
 * @author ZhangShenao
 * @date 2024/3/21
 * @description <a href="https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/">...</a>
 */
public class Leetcode129_求根节点到叶子节点的数字之和 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 采用递归算法实现
     * 对二叉树进行递归dfs遍历,并在递归函数中传入之前的和preSum,在遍历过程中累加preSum和当前节点值
     * 如果到达叶子节点,则返回preSum*10+节点值
     * 如果到达非叶子节点,累加preSum,并继续递归遍历左、右子树
     */
    public int sumNumbers(TreeNode root) {
        //调用递归处理
        return dfs(root, 0);
    }

    /**
     * 递归实现
     * 对树进行dfs遍历,并传入前缀节点列表
     */
    private int dfs(TreeNode node, int preSum) {
        //递归终止条件
        if (node == null) {
            return 0;
        }

        //累加当前节点值
        preSum = preSum * 10 + node.val;

        //到达叶子节点,直接返回preSUm
        if (node.left == null && node.right == null) {
            return preSum;
        }

        //到达非叶子节点,继续递归遍历左、右子树
        return dfs(node.left, preSum) + dfs(node.right, preSum);
    }
}
